/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package trash;
import java.lang.Math;
import java.util.Random;
import java.util.Arrays;

/*linyi*/
import java.io.FileReader;


/**
 *
 * @author Ryan
 */
public class FMMIdentification{
    //three types of states
    enum State {
        C,E,R;
        private final static State [] state = values();
        public static State toState(int n) {return state [n];}
        public int toInt() {return ordinal();}
        public static int cardinality() {return state.length;}
    }
    //three types of outputs
    enum Output {
        c,e,r;
        private final static Output [] output = values();
        public static Output toOutput(int n) {return output[n];}
        public int toInt() {return ordinal();}
        public static int cardinality() {return output.length;}
    }
    //hard coded state transition matrix
    static double [][] T ={
                            //{0.83,0.17,0.0},
                            {0.85,0.15,0.0},
                            //{0.0,0.81,0.19},
                            {0,0.82,0.18},
                            //{0,0,1},
                            {0.0,0.0,1.0},
                           };
   //hard coded state output matrix
   //first index is tate, second is output
    static double [][] outProb = {
                                //{0.86,0.14,0.0},
                                {0.88,0.12,0.0},
                                //{0.554,0.338,0.108},
                                {0.56,0.38,0.06},
                                //{0.029,0.381,0.59},
                                {0.04,0.40,0.56},
                                 };
/**
 *  simulate FMM for given number of cycles.
 *
 * @param N the number of cycles of output we want
 * @return array of N outputs
 */
  static Output [] getTrace (int N)
  {
      Output [] result = new Output[N];
      State currentState = State.C;
      State nextState = null;
      for (int i=0; i<N; i++) {
          //must use aRandom to get this random number, a plain call
          //to Math.random is not deterministic
          double outputProb = aRandom.nextDouble();
          for (int k=0; k < Output.cardinality(); k++) {
          if ( outProb[currentState.toInt()][k] > outputProb) {
              result[i] = Output.toOutput(k);
              break;
              } else {
                outputProb -= outProb[currentState.toInt()][k];
              }
          }
          //must use aRandom to get this random number, a plain call
          //to Math.random is not deterministic
          double transProb = aRandom.nextDouble();
          for ( int k=0; k< State.cardinality(); k++) {
            if (T[currentState.toInt()][k] > transProb) {
                nextState = State.toState(k);
                break;
            } else {
                transProb -= T[currentState.toInt()][k];
            }
          }
          currentState = nextState;
        }
        return result;
       }
       //initalize a 2D arra - each row has equal probability
       static void uniformInit (double [][] A)
       {
           for ( int i=0 ; i < A.length ; i++ ) {
               double unitDist = 1.0/ (double) A[i].length;
               Arrays.fill(A[i], unitDist);
           }
       }
       /** used for random number generation in the perturb routines.
        * seeded to 0 to ensure determinism across runs
        *
        * @see also perturb
        */
       static Random aRandom = new Random( 997L);
       /**
        * Create a new version of A, with two
        * entires in a single row perturbed. Guaranteed
        * to preserve the invariant that the row entires sum
        * to 1, and that each entry is within [0,1]
        */
        static double [][] perturb(double [][] A, double perturbFactor)
    {
            //warning- very expensive copy, should to store
            //state to just change A, and undo if does not lead
            //to better solution
            double [][] result = new double [A.length][A[0].length];
            for (int i = 0; i < A.length;i++) {
                for (int j=0; j < A[0].length; j++) {
                    result [i][j] = A[i][j];
                }
            }
            int r = aRandom.nextInt(A.length);
            int c0 = aRandom.nextInt(A[r].length);
            int c1 = aRandom.nextInt(A[r].length);

            double l = Math.min(A[r][c0], A[r][c1]);
            double max = Math.max(A[r][c0], A[r][c1]);
            double u = 1.0 - max;
            double delta = Math.min(l, u);
            double randUnit = (aRandom.nextInt() % 2 ==1) ? 1.0 : -1.0;
            delta *= randUnit;
            System.out.println("Random params: "+ r + " " + c0 + " " + c1
                    + " " + randUnit );
            result [r][c0] += delta * perturbFactor;
            result [r][c1] -= delta * perturbFactor;
            return result;
    }
    static double computeFom(Output [] trace, double [][] T,
                                double [][] O)
    {
        int numStates = T.length;
        double [] initDist = new double [numStates];
        //all states are equally likely at first
        //double uniformDist =1.0/ (double) numState;
        //Arrays.fill(p[0], uniformDist);
        //always start in the C state;
        initDist [State.C.toInt()] = 1.0;

        double [] terms = new double [T.length];
        double [][] outprob = new double [trace.length][T.length];
        double [][] logoutprob = new double [trace.length][T.length];
        for ( int i = 0 ; i < trace.length ; i++) {
            if ( i ==0) {
                for (int j = 0; j < numStates; j++ ) {
                   outprob[i][j] = initDist [j]*O[j][trace[i].toInt()];
                   //TODO: very poor choice of names- outprob & outProb
                   //have already aliased with disastrous results once
                }
                for (int j = 0; j < numStates; j++) {
                    logoutprob [i][j] = Math.log(outprob[i][j]);
                }
              } else {
                for ( int j = 0 ; j < numStates; j++) {
                    for (int k = 0; k < numStates; k++) {
                        outprob[i][j] += outprob[i-1][k] * T[k][j]
                                * O[j][trace[i].toInt()];
                        //TODO: not sure if setting terms correctly
                        terms[k] = logoutprob [i-1][k]
                                    + Math.log(T[k][j])
                                    + Math.log(O[j][trace[i].toInt()]);
                        if ( Double.isNaN(terms [k]) ) {
                            System.out.println("Hack:" + i + "," + j + " "
                                    + logoutprob[i-1][k] + " "+ Math.log(T[k][j])
                                    + " " + Math.log(O[j][trace[i].toInt()]) );
                        }
                    }
                    logoutprob [i][j] = logsum (terms);
                }
              }
            }
            double totalprob = 0.0 ;
            for ( int j = 0; j < numStates; j++) {
                totalprob += outprob [trace.length-1][j];
            }
            System.out.println("returned from : " + totalprob);
            double totalProbFromLogs = 0.0;
            for ( int j = 0; j < numStates; j++) {
                totalProbFromLogs += Math.exp( logoutprob[trace.length-1][j] );
            }
            System.out.println("fom as computed by totalProbFromLogs : " +
                    totalProbFromLogs );
            return totalprob;
        }
     static double logsum( double [ ] terms) {

        double result = 0;
        int i;
        for ( i = 0 ; i < terms.length; i++ ){
            if (terms [i] != Double.NEGATIVE_INFINITY) {
                break ;
            }
        }
        if( i == terms.length) {
            return Double.NEGATIVE_INFINITY;
        }

        double mu = 0.0;
        for (i = 0; i < terms.length; i ++){
            mu = (terms[i] != Double.NEGATIVE_INFINITY)
                    && (terms[i] < mu) ? terms[i] : mu;
        }
        double tmp = 0.0;

        for(i = 0; i < terms.length; i ++) {
            tmp += Math.exp( terms[i] - mu);
        }

        result = mu + Math.log(tmp);
        return result;
    }

    static public void print(String s, double [][]A) {
        System.out.println(s);
        for( int i = 0; i < A.length; i ++) {
            for(int j = 0; j < A[i].length; j ++) {
                System.out.printf("%.2f\n", A[i][j]);
            }
        }
    }

    static public void print (String s, double [][] A, double [][] B) {
        assert(A.length == B.length);
        System.out.println(s);

        for (int i = 0; i < A.length; i ++) {
            for (int j = 0; j < A[i].length; j ++) {
                System.out.printf("%.2f\n", Math.abs(A[i][j] - B[i][j])/B[i][j]);
            }
            System.out.println();
        }
    }

    static final double initPerturbFactor = 0.3;
    static final int numPerturbsPerValue = 10;
    static final double updateFactor = 2.0;
    static final double minPerturbFactor = 0.01;

    static public void learnFMM( Output[] trace) {
        double [][] Tsolve = new double[State.cardinality()][State.cardinality()];
        double [][] Osolve = new double[State.cardinality()][Output.cardinality()];
        uniformInit(Tsolve);
        uniformInit(Osolve);

        Tsolve = T;
        Osolve = outProb;

        double perturbFactor = initPerturbFactor;
        int numPerturb = numPerturbsPerValue;
        int unsuccPerturb = 0;
        while (true) {
            double fom = computeFom(trace, Tsolve, Osolve);
            double [][] Tnew = perturb( Tsolve, perturbFactor);
            double [][] Onew = perturb( Osolve, perturbFactor);

            double newfom = computeFom(trace, Tnew, Onew);
            if(newfom > fom){
                Tsolve = Tnew;
                Osolve = Onew;
            } else {
                unsuccPerturb ++;
            }

            if( unsuccPerturb > numPerturb ) {
                perturbFactor /= updateFactor;
                unsuccPerturb = 0;
            }
            if(perturbFactor < minPerturbFactor) {
                break;
            }
        }
        print("Learned_T/Actual_T:", Tsolve, T);
        print("learned_O/Actural_O:", Osolve, outProb);
    }

    static final int defaultTraceLength = 10;

    static final int inputs[] = {0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,2,2,2,1,2,2,2,2,1,2,2,2,0,1,2,1,2,2,1};
    static Output[] getOutputsFromInput(int[] inputs){
        Output[] result = new Output[inputs.length];
        for(int i = 0; i < inputs.length; i ++) {
            if (inputs[i] == 0)
                result[i] = Output.toOutput(0);
            else if (inputs[i] == 1)
                result[i] = Output.toOutput(1);
            else if (inputs[i] == 2)
                result[i] = Output.toOutput(2);
        }
        return result;
    }

    static Output[] readObservationFromFile(String Filename){
        try {
            FileReader reader = new FileReader(Filename);
            char[] inputs = new char[256];
            int length = reader.read(inputs);

            Output[] result = new Output[length/2 - 1];

            for (int i = 0, j = 0; i < length;){
                if(inputs[i] == ' ') {
                    i ++;
                    continue;
                }
                if(inputs[i] == 'c') {
                    result[j] = Output.toOutput(0);
                } else if (inputs[i] == 'e') {
                    result[j] = Output.toOutput(1);
                } else if (inputs[i] == 'r') {
                    result[j] = Output.toOutput(2);
                } else break;
                i ++;
                i ++;
                j ++;
            }
            return result;
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    static public void main ( String[] args) {
        
        int N = defaultTraceLength;
        if(args.length != 0) {
            N = Integer.parseInt(args[0]);
        }
        for (int j =0; j < 10; j++) {
        Output[] testTrace = getTrace(25+j);
        System.out.println("");
        for (int i = 0; i < testTrace.length; i ++) {
            System.out.print(""+testTrace[i]+";");
        }
        }
       // learnFMM(testTrace);
        return;
    }

}
